Prefetching is a technique to fetch data ahead of time before the input/output (I/O) access request for that data arrives so that the cost of a cache miss, e.g. having to fetch data in the I/O path, can be avoided. Prefetching can be classified into two broad categories: (1) sequential prefetching; and (2) history based prefetching. One other dimension in prefetching is to determine the amount of data to be prefetched. While sequential prefetching works well for workloads that are dominated by sequential accesses, history-based prefetching is useful for workloads that have random data accesses and repeating patterns of accesses.
Existing prefetching techniques primarily do sequential prefetching. Though simple and effective, in the context of caching for cloud storage, given variable and high latency accesses over a WAN network, they are not efficient. These techniques cannot capture or exploit semantic correlation across random accesses. Examples of these semantic-correlations include inter-file dependencies, file metadata and data accesses, database indices and table data. Moreover, in the case of cloud storage caching, the penalty for a wrong prefetch decision is very high in terms of both performance and cost.
There also are several history-based prefetching schemes that are file-based, such as “Design and Implementation of a Predictive File Prefetching Algorithm” by Kroeger et. al. that uses a technique called Extended Partition Context Modelling which takes into account the prefetch lead time. Another similar technique has been proposed by Griffieon et. al. in “Reducing File System Latency using a Predictive Approach,” which uses a “lookahead period” as the criterion to relate file accesses. But these approaches are coarse-grained since they are based on files not blocks, and also do not consider important factors such as prefetch wastage and cost of a prefetch. Working at a file granularity has several drawbacks: a) metadata prefetching is not possible if the metadata of the file system is not stored in the form of files, and b) prefetching cost is increased due to “prefetch wastage” by bringing into the cache the entire file's data even though some of the blocks of the file may not be seen in the client's request stream. Also, most history-based prefetching schemes are not adaptive and do not dynamically vary the amount of data to prefetch and what data to prefetch, but use a coarse-grained fixed threshold to cut off what to bring into the cache.
Another approach is discussed in “A Prefetching Scheme Exploiting Both Data Layout and Access History on the Disk” by Song et al. This approach functions at block-granularity and also takes into account history information. However, while this system tries to minimize the penalty of a mis-prefetch, it does not adapt it with a heuristic, but simply uses a boundary for the mis-prefetch percent to continue or stop prefetching altogether. It is also not sensitive to the time of prefetch, e.g., when to initiate a prefetch such that cache hits are maximized without incurring wasted prefetches.
Yet another approach constructs and uses an access history graph and is described in U.S. patent application Ser. No. 13/951,662, entitled, “Systems and Methods for Adaptive Prefetching, which is herein incorporated by reference in its entirety.